Noise and/or any form of interference frequently cause the distortion of data in storage and transmission systems.
Error correcting codes deal with reliable transmission and/or storage of data by incorporating some redundant information in the original data. This redundancy enables recovering the original information or at least detecting the presence of errors, even if errors occur up to some tolerance levels.
Error correcting codes are implemented in several digital communication devices and systems to compensate for errors and to provide error-resistant delivery of digital data during its storage and/or transmission.
Exemplary devices implementing error correcting codes comprise computers, disks, cellular phones, base stations, etc. Exemplary applications of error correcting codes comprise transmission systems such as wireless ad-hoc networks (e.g. standardized in Wi-Fi 802.11), radio communication systems (e.g. in 3G, 4G/LTE, 5G and beyond), optical fiber-based transmission systems, and digital video broadcasting (e.g. standardized in DVB-C2, DVB-S2X, and DVB-T2). Non-binary error correcting codes are particularly used in applications requiring a high spectral efficiency.
Existing error correcting codes comprise linear codes, generally categorized into linear block codes and convolutional codes. Linear codes refer to codes that satisfy a linearity property according to which any linear combination of codeword vectors is a codeword vector. Linear block codes are widely used because they are less complex and easier to implement than non-linear codes. Exemplary linear block codes comprise Hamming codes, Reed-Solomon codes, Turbo codes and low-density parity-check (LDPC) codes.
LDPC codes are very efficient linear block codes that can provide high transmission rates that approach the optimum channel capacity, i.e. the theoretical maximum amount of information that can be transmitted over a communication channel. In particular, non-binary LDPC codes are very efficient to provide high-spectral efficiency coding and can achieve better error-correction performance than binary LDPC codes.
Any linear error correcting code can be represented by a generator matrix and a parity-check matrix. The entries (also referred to as ‘coefficients’) of the generator and parity-check matrices belong to the algebraic structure over which the error correcting code is constructed.
The generator matrix is used in the encoding process to generate codeword vectors. The values of the components of each codeword vector depend thus on the entries of the generator matrix (equivalently on the entries of the parity-check matrix).
The non-zero entries of the parity-check matrix define the parity-check equations designed to be satisfied by the codeword vectors. In addition, the parity-check matrix can be used in the decoding process. In particular, iterative decoders such as the Belief Propagation (BP) algorithm use a graph associated with the code known as the ‘Tanner graph’. The positions of the non-zero entries of the parity-check matrix lead to the structure of the Tanner graph and its topological properties such as the number of cycles in the Tanner graph associated with the code. As cycles impact the decoding error performance (efficient codes have a small number of short cycles), the positions of the non-zero entries of the parity-check matrix need to be carefully chosen so as to minimize the number of cycles.
Accordingly, the construction of the parity-check matrix of non-binary linear error correcting codes can be performed in two steps.
In a first step, the positions of the non-zero entries of the parity-check matrix are optimized in order to minimize the impact of cycles on the decoding process. Exemplary algorithms that can be used to achieve this step comprise the ‘Progressive Edge Growth’ algorithm disclosed in “X.-Y. Hu, E. Eleftheriou, and D. M. Arnold, Regular and Irregular Progressive Edge-Growth Tanner Graphs, IEEE Transactions on Information Theory, Volume 51, pages 386-298, 2005”.
In a second step, the values of the non-zero entries of the parity-check matrix are determined. These values may, for example, be selected randomly from a uniform distribution as disclosed in “X.-Y. Hu, E. Eleftheriou, and D. M. Arnold, Regular and Irregular Progressive Edge-Growth Tanner Graphs, IEEE Transactions on Information Theory, Volume 51, pages 386-298, 2005”. Alternatively, the values of the non-zero entries can be selected according to specific design criteria such as the maximization of the marginal entropy of elements of the syndrome vector as disclosed in “D. Mackay, Optimizing Sparse Graph Codes over GF(q), available on line, 2003”.
Digital modulation techniques convert a digital signal into a modulated signal in the form of a sequence of modulated symbols represented as signal points that belong to a signal constellation (also referred to as ‘constellation diagram’). The signal constellation depends on the modulation scheme used and represents the values that can be taken by each symbol as points in the Euclidean space. The components of the digital signal are mapped onto symbols using a modulation mapping which associates a symbol from the signal constellation with each value of the digital signal. Exemplary digital modulation schemes comprise amplitude-shift keying (ASK), frequency-shift keying (FSK), phase-shift keying (PSK), and quadrature amplitude modulation (QAM). Exemplary modulation mappings comprise the Gray mapping which uses a binary representation of the components of the digital signal.
The concatenation of error correcting codes and modulation provides a coded modulation. In coded modulations, coding can be seen as a patterning of the continuous time signals, their phases and/or their amplitudes.
When a coded modulation is used, data is mapped onto sequences of symbols using modulation mappings, introducing redundancy to improve error performance. Codeword vectors are mapped onto points in the signal constellation in a way that enhances the distance properties of the error correcting code. The resulting modulated codeword vector can be seen as a vector of signal points (constellation points). The distance between any two modulated codeword vectors can be determined from the Euclidean distance between the signal points representing each vector in the Euclidean Space. For binary modulations, the Hamming distance of the error correcting code is equivalent to the Euclidean distance of the modulated codeword vectors. The values and the positions of the non-zero entries of the parity-check matrix can be optimized as described above in a way that maximizes the Hamming distance of the code.
For non-binary modulations, the Euclidean distance of modulated codeword vectors is not equivalent to the Hamming distance of the error correcting code. In addition, the Euclidean distance properties depend on the modulation mapping used to map the codeword vectors onto signal points. As a result, the construction of parity-check matrices of non-binary error correcting codes for coded modulations according to the maximization of the Hamming distance is sub-optimal. There is accordingly a need for constructing efficient non-binary coded modulations involving error correcting codes that are optimized for the Euclidean distance rather than the Hamming distance and are adapted to the modulation mapping and signal modulations that are used.